package com.xj.algorithm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 杨辉三角II
 */
public class L119_杨辉三角的第k行 {

    /**
     * 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。超过34时，int的最大值装不下了
     *
     * 在杨辉三角中，每个数是它左上方和右上方的数的和。
     *
     * 示例:
     *
     * 输入: 3
     * 输出: [1,3,3,1]
     */
    public static void main(String[] args) {
        System.out.println(getRow(3));
    }

    //自己的解法：动态规划。注意它是从0开始标记的行号
    public static List<Integer> getRow(int rowIndex) {
        rowIndex++;
        List<List<Integer>> triangle = new ArrayList<>();
        if (rowIndex == 0) {
            return new ArrayList<>();
        }

        triangle.add(new ArrayList<>());
        triangle.get(0).add(1);

        //从第2行开始处理。默认其他位置是0
        for (int rowNum = 1; rowNum < rowIndex; rowNum++) {
            List<Integer> row = new ArrayList<>();
            List<Integer> prevRow = triangle.get(rowNum-1);

            row.add(1);
            for (int j = 1; j < rowNum; j++) {
                row.add(prevRow.get(j-1) + prevRow.get(j));
            }
            row.add(1);
            triangle.add(row);
        }
        return triangle.get(rowIndex-1);
    }

    //官方解法：数学公式[1,4,6,4,1] = [0,1,3,3,1] + [1,3,3,1,0]。本质是错位相加
    //但是还是需要双重循环
    //也可以用组合数公式
    public static List<Integer> getRowOffice(int rowIndex) {
        List<Integer> pre = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();

        for (int i = 0; i <= rowIndex; i++) {
            cur = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    cur.add(1);
                } else {
                    cur.add(pre.get(j - 1) + pre.get(j));
                }
            }
            pre = cur;
        }
        return cur;
    }

}
